package com.fmm.medium;

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class NumGame {

    /**
     * 递归实现
     *
     * @param t 目标数字
     * @param used 已使用的数字
     * @param unused 未使用的数字
     * @return 是否先选牌者获胜
     */
    public static boolean firstWin(
            Integer t, Set<Integer> used,
            Set<Integer> unused) {
        // 计算出当前已使用过的牌的总和
        Integer currentSum = used.stream().collect(Collectors.summingInt(x -> x));
        for (Integer unusedCard : unused) {
            // 如果已使用过的数字之和 + 未使用的数字 >= 目标，先选牌获胜
            if (currentSum + unusedCard >= t) {
                return true;
            }
            // 把当前卡牌加入已使用，并从未使用中扣除，进行递归调用
            Set<Integer> newUsed = new HashSet<>(used);
            newUsed.add(unusedCard);
            Set<Integer> newUnused = new HashSet<>(unused);
            newUnused.remove(unusedCard);
            // 如果下层是后选牌者获胜，即表示当前选牌者获胜
            if (!firstWin(t, newUsed, newUnused)) {
                return true;
            }
        }
        // 所有未使用牌都尝试过之后，如果都没有返回，表示后选牌者获胜
        return false;
    }

    public static void main(String[] args) {
        Integer t = 3;
        Integer cardCount = 2;
        Set<Integer> used = new HashSet<>();
        Set<Integer> unused = new HashSet<>();
        for (int i = 1; i <= cardCount; i++) {
            unused.add(i);
        }
        System.out.println(firstWin(t, used, unused));
    }
}
